class Solution:
    def solveNQueens(self, n: int):
        
        queens=[-1]*n #初始化表示某一行皇后可能在的位置
        row=["."]*n #初始化某一行每个位置都为“ .”
        
        col=set() #列
        dial1=set() #主对角线
        dial2=set() #次对角线        
               
        #得到最后结果
        def generateBoard():
            board=list()
            for i in range(n): #遍历行 0到n-1行
                row[queens[i]]="Q"
                #表示当前行中，皇后的位置为第queens[i]列，并将" . " 替换为Q
                board.append("".join(row))
                #将该行结果合并成一个字符串，返回到board这个列表中，相当于borad每个元素是一行放置皇后的情况
                row[queens[i]]="." #复位，以便下一行修改
            return board
        
        #
        def backtrack(row):
            if row==n:
                board=generateBoard()
                solutions.append(board) #如果row==n说明已经到了叶子节点，遍历完了都符合条件，则把符合条件的情况加到solutions
            else:
                for i in range(n): #i表示在第几列
                    if i in col or row-i in dial1 or row+i in dial2:
                        continue  #如果在同一列、对角线上，则跳过
                    else:
                        queens[row]=i #将第row行皇后所在的第i列记录下来
                        col.add(i)       
                        dial1.add(row-i) 
                        dial2.add(row+i) #占位
                        backtrack(row+1) #遍历下一行
                        col.remove(i)
                        dial1.remove(row-i)
                        dial2.remove(row+i)  #返回上一行时要复位
        

        solutions=list()
        backtrack(0)
        return solutions

a=Solution()
print(a.solveNQueens(4))